/**
 * @a https://leetcode.cn/problems/n-queens-ii/submissions/656773892/
 */

#include "../common.h"

class Solution {
private:
    int ret = 0;
    int sz;
public:
    int totalNQueens(int n) {
        sz = n;
        dfs(0,0,0,0);
        return ret;
    }
    void dfs(int row, int col, int ldiag, int rdiag){
        if(sz == row){
            ++ret;
            return;
        }
        int bits = ((1 << sz) - 1) /*创建 n 个 ‘1’ 位*/ & ~(col | ldiag | rdiag); // 排除不能选的
        while(bits){
            int pick = bits & -bits; // 从右往左开始选，pick 最右边的为 1 的位
            dfs(row + 1, col | pick, (ldiag | pick) << 1, (rdiag | pick) >> 1);
            bits &= bits - 1; // 复原最右边的为 1 位为 0，也就是 de_pick
        }
    }
};